home *** CD-ROM | disk | FTP | other *** search
/ Tricks of the Mac Game Programming Gurus / TricksOfTheMacGameProgrammingGurus.iso / More Source / C⁄C++ / Peter's Final Project / jpeg-5b / structure.doc < prev    next >
Text File  |  1995-03-10  |  47KB  |  865 lines

  1. IJG JPEG LIBRARY:  SYSTEM ARCHITECTURE
  2.  
  3. Copyright (C) 1991-1995, Thomas G. Lane.
  4. This file is part of the Independent JPEG Group's software.
  5. For conditions of distribution and use, see the accompanying README file.
  6.  
  7.  
  8. This file provides an overview of the architecture of the IJG JPEG software;
  9. that is, the functions of the various modules in the system and the interfaces
  10. between modules.  For more precise details about any data structure or calling
  11. convention, see the include files and comments in the source code.
  12.  
  13. We assume that the reader is already somewhat familiar with the JPEG standard.
  14. The README file includes references for learning about JPEG.  The file
  15. libjpeg.doc describes the library from the viewpoint of an application
  16. programmer using the library; it's best to read that file before this one.
  17. Also, the file coderules.doc describes the coding style conventions we use.
  18.  
  19. In this document, JPEG-specific terminology follows the JPEG standard:
  20.   A "component" means a color channel, e.g., Red or Luminance.
  21.   A "sample" is a single component value (i.e., one number in the image data).
  22.   A "coefficient" is a frequency coefficient (a DCT transform output number).
  23.   A "block" is an 8x8 group of samples or coefficients.
  24.   An "MCU" (minimum coded unit) is an interleaved set of blocks of size
  25.     determined by the sampling factors, or a single block in a
  26.     noninterleaved scan.
  27. We do not use the terms "pixel" and "sample" interchangeably.  When we say
  28. pixel, we mean an element of the full-size image, while a sample is an element
  29. of the downsampled image.  Thus the number of samples may vary across
  30. components while the number of pixels does not.  (This terminology is not used
  31. rigorously throughout the code, but it is used in places where confusion would
  32. otherwise result.)
  33.  
  34.  
  35. *** System features ***
  36.  
  37. The IJG distribution contains two parts:
  38.   * A subroutine library for JPEG compression and decompression.
  39.   * cjpeg/djpeg, two simple applications that use the library to transform
  40.     JFIF JPEG files to and from several other image formats.
  41. cjpeg/djpeg are of no great intellectual complexity: they merely add a simple
  42. command-line user interface and I/O routines for several uncompressed image
  43. formats.  This document concentrates on the library itself.
  44.  
  45. We desire the library to be capable of supporting all JPEG baseline and
  46. extended sequential DCT processes.  Progressive processes are also allowed
  47. for in the system architecture, although they are not likely to be
  48. implemented very soon.  Hierarchical processes are not supported.
  49.  
  50. The library does not support the lossless (spatial) JPEG process.  Lossless
  51. JPEG shares little or no code with lossy JPEG, and would normally be used
  52. without the extensive pre- and post-processing provided by this library.
  53. We feel that lossless JPEG is better handled by a separate library.
  54.  
  55. Within these limits, any set of compression parameters allowed by the JPEG
  56. spec should be readable for decompression.  (We can be more restrictive about
  57. what formats we can generate.)  Although the system design allows for all
  58. parameter values, some uncommon settings are not yet implemented and may
  59. never be; nonintegral sampling ratios are the prime example.  Furthermore,
  60. we treat 8-bit vs. 12-bit data precision as a compile-time switch, not a
  61. run-time option, because most machines can store 8-bit pixels much more
  62. compactly than 12-bit.
  63.  
  64. For legal reasons, JPEG arithmetic coding is not currently supported, but
  65. extending the library to include it would be straightforward.
  66.  
  67. By itself, the library handles only interchange JPEG datastreams --- in
  68. particular the widely used JFIF file format.  The library can be used by
  69. surrounding code to process interchange or abbreviated JPEG datastreams that
  70. are embedded in more complex file formats.  (For example, we anticipate that
  71. Sam Leffler's TIFF library will use this code to support the revised TIFF
  72. JPEG format.)
  73.  
  74. The library includes a substantial amount of code that is not covered by the
  75. JPEG standard but is necessary for typical applications of JPEG.  These
  76. functions preprocess the image before JPEG compression or postprocess it after
  77. decompression.  They include colorspace conversion, downsampling/upsampling,
  78. and color quantization.  This code can be omitted if not needed.
  79.  
  80. A wide range of quality vs. speed tradeoffs are possible in JPEG processing,
  81. and even more so in decompression postprocessing.  The decompression library
  82. provides multiple implementations that cover most of the useful tradeoffs,
  83. ranging from very-high-quality down to fast-preview operation.  On the
  84. compression side we have generally not provided low-quality choices, since
  85. compression is normally less time-critical.  It should be understood that the
  86. low-quality modes may not meet the JPEG standard's accuracy requirements;
  87. nonetheless, they are useful for viewers.
  88.  
  89.  
  90. *** Portability issues ***
  91.  
  92. Portability is an essential requirement for the library.  The key portability
  93. issues that show up at the level of system architecture are:
  94.  
  95. 1.  Memory usage.  We want the code to be able to run on PC-class machines
  96. with limited memory.  Images should therefore be processed sequentially (in
  97. strips), to avoid holding the whole image in memory at once.  Where a
  98. full-image buffer is necessary, we should be able to use either virtual memory
  99. or temporary files.
  100.  
  101. 2.  Near/far pointer distinction.  To run efficiently on 80x86 machines, the
  102. code should distinguish "small" objects (kept in near data space) from
  103. "large" ones (kept in far data space).  This is an annoying restriction, but
  104. fortunately it does not impact code quality for less brain-damaged machines,
  105. and the source code clutter turns out to be minimal with sufficient use of
  106. pointer typedefs.
  107.  
  108. 3. Data precision.  We assume that "char" is at least 8 bits, "short" and
  109. "int" at least 16, "long" at least 32.  The code will work fine with larger
  110. data sizes, although memory may be used inefficiently in some cases.  However,
  111. the JPEG compressed datastream must ultimately appear on external storage as a
  112. sequence of 8-bit bytes if it is to conform to the standard.  This may pose a
  113. problem on machines where char is wider than 8 bits.  The library represents
  114. compressed data as an array of values of typedef JOCTET.  If no data type
  115. exactly 8 bits wide is available, custom data source and data destination
  116. modules must be written to unpack and pack the chosen JOCTET datatype into
  117. 8-bit external representation.
  118.  
  119.  
  120. *** System overview ***
  121.  
  122. The compressor and decompressor are each divided into two main sections:
  123. the JPEG compressor or decompressor proper, and the preprocessing or
  124. postprocessing functions.  The interface between these two sections is the
  125. image data that the official JPEG spec regards as its input or output: this
  126. data is in the colorspace to be used for compression, and it is downsampled
  127. to the sampling factors to be used.  The preprocessing and postprocessing
  128. steps are responsible for converting a normal image representation to or from
  129. this form.  (Those few applications that want to deal with YCbCr downsampled
  130. data can skip the preprocessing or postprocessing step.)
  131.  
  132. Looking more closely, the compressor library contains the following main
  133. elements:
  134.  
  135.   Preprocessing:
  136.     * Color space conversion (e.g., RGB to YCbCr).  This step may also
  137.       provide gamma adjustment.
  138.     * Edge expansion and downsampling.  Optionally, this step can do simple
  139.       smoothing --- this is often helpful for low-quality source data.
  140.   JPEG proper:
  141.     * MCU assembly, DCT, quantization.
  142.     * Entropy coding (Huffman or arithmetic).
  143.  
  144. In addition to these modules we need overall control, marker generation,
  145. and support code (memory management & error handling).  There is also a
  146. module responsible for physically writing the output data --- typically
  147. this is just an interface to fwrite(), but some applications may need to
  148. do something else with the data.
  149.  
  150. The decompressor library contains the following main elements:
  151.  
  152.   JPEG proper:
  153.     * Entropy decoding (Huffman or arithmetic).
  154.     * Dequantization, inverse DCT, MCU disassembly.
  155.   Postprocessing:
  156.     * Upsampling.  Optionally, this step may be able to do more general
  157.       rescaling of the image.
  158.     * Color space conversion (e.g., YCbCr to RGB).  This step may also
  159.       provide gamma adjustment.
  160.     * Optional color quantization (e.g., reduction to 256 colors).
  161.     * Optional color precision reduction (e.g., 24-bit to 15-bit color).
  162.       [Not implemented in v5.]
  163.  
  164. We also need overall control, marker parsing, and a data source module.
  165. The support code (memory management & error handling) can be shared with
  166. the compression half of the library.
  167.  
  168. There may be several implementations of each of these elements, particularly
  169. in the decompressor, where a wide range of speed/quality tradeoffs is very
  170. useful.  It must be understood that some of the best speedups involve
  171. merging adjacent steps in the pipeline.  For example, upsampling, color space
  172. conversion, and color quantization might all be done at once when using a
  173. low-quality ordered-dither technique.  The system architecture is designed to
  174. allow such merging where appropriate.
  175.  
  176.  
  177. Note: it is convenient to regard edge expansion (padding to block boundaries)
  178. as a preprocessing/postprocessing function, even though the JPEG spec includes
  179. it in compression/decompression.  We do this because downsampling/upsampling
  180. can be simplified a little if they work on padded data: it's not necessary to
  181. have special cases at the right and bottom edges.  Therefore the interface
  182. buffer is always an integral number of blocks wide and high, and we expect
  183. compression preprocessing to pad the source data properly.  Padding will occur
  184. only to the next block (8-sample) boundary.  In an interleaved-scan situation,
  185. additional dummy blocks may be used to fill out MCUs, but the MCU assembly and
  186. disassembly logic will create or discard these blocks internally.  (This is
  187. advantageous for speed reasons, since we avoid DCTing the dummy blocks.
  188. It also permits a small reduction in file size, because the compressor can
  189. choose dummy block contents so as to minimize their size in compressed form.)
  190. Applications that wish to deal directly with the downsampled data must provide
  191. similar buffering and padding for odd-sized images.
  192.  
  193.  
  194. *** Poor man's object-oriented programming ***
  195.  
  196. It should be clear by now that we have a lot of quasi-independent processing
  197. steps, many of which have several possible behaviors.  To avoid cluttering the
  198. code with lots of switch statements, we use a simple form of object-style
  199. programming to separate out the different possibilities.
  200.  
  201. For example, two different color quantization algorithms could be implemented
  202. as two separate modules that present the same external interface; at runtime,
  203. the calling code will access the proper module indirectly through an "object".
  204.  
  205. We can get the limited features we need while staying within portable C.
  206. The basic tool is a function pointer.  An "object" is just a struct
  207. containing one or more function pointer fields, each of which corresponds to
  208. a method name in real object-oriented languages.  During initialization we
  209. fill in the function pointers with references to whichever module we have
  210. determined we need to use in this run.  Then invocation of the module is done
  211. by indirecting through a function pointer; on most machines this is no more
  212. expensive than a switch statement, which would be the only other way of
  213. making the required run-time choice.  The really significant benefit, of
  214. course, is keeping the source code clean and well structured.
  215.  
  216. We can also arrange to have private storage that varies between different
  217. implementations of the same kind of object.  We do this by making all the
  218. module-specific object structs be separately allocated entities, which will
  219. be accessed via pointers in the master compression or decompression struct.
  220. The "public" fields or methods for a given kind of object are specified by
  221. a commonly known struct.  But a module's initialization code can allocate
  222. a larger struct that contains the common struct as its first member, plus
  223. additional private fields.  With appropriate pointer casting, the module's
  224. internal functions can access these private fields.  (For a simple example,
  225. see jdatadst.c, which implements the external interface specified by struct
  226. jpeg_destination_mgr, but adds extra fields.)
  227.  
  228. (Of course this would all be a lot easier if we were using C++, but we are
  229. not yet prepared to assume that everyone has a C++ compiler.)
  230.  
  231. An important benefit of this scheme is that it is easy to provide multiple
  232. versions of any method, each tuned to a particular case.  While a lot of
  233. precalculation might be done to select an optimal implementation of a method,
  234. the cost per invocation is constant.  For example, the upsampling step might
  235. have a "generic" method, plus one or more "hardwired" methods for the most
  236. popular sampling factors; the hardwired methods would be faster because they'd
  237. use straight-line code instead of for-loops.  The cost to determine which
  238. method to use is paid only once, at startup, and the selection criteria are
  239. hidden from the callers of the method.
  240.  
  241. This plan differs a little bit from usual object-oriented structures, in that
  242. only one instance of each object class will exist during execution.  The
  243. reason for having the class structure is that on different runs we may create
  244. different instances (choose to execute different modules).  You can think of
  245. the term "method" as denoting the common interface presented by a particular
  246. set of interchangeable functions, and "object" as denoting a group of related
  247. methods, or the total shared interface behavior of a group of modules.
  248.  
  249.  
  250. *** Overall control structure ***
  251.  
  252. We previously mentioned the need for overall control logic in the compression
  253. and decompression libraries.  In IJG implementations prior to v5, overall
  254. control was mostly provided by "pipeline control" modules, which proved to be
  255. large, unwieldy, and hard to understand.  To improve the situation, the
  256. control logic has been subdivided into multiple modules.  The control modules
  257. consist of:
  258.  
  259. 1. Master control for module selection and initialization.  This has two
  260. responsibilities:
  261.  
  262.    1A.  Startup initialization at the beginning of image processing.
  263.         The individual processing modules to be used in this run are selected
  264.         and given initialization calls.
  265.  
  266.    1B.  Per-pass control.  This determines how many passes will be performed
  267.         and calls each active processing module to configure itself
  268.         appropriately at the beginning of each pass.  End-of-pass processing,
  269.     where necessary, is also invoked from the master control module.
  270.  
  271.    Method selection is partially distributed, in that a particular processing
  272.    module may contain several possible implementations of a particular method,
  273.    which it will select among when given its initialization call.  The master
  274.    control code need only be concerned with decisions that affect more than
  275.    one module.
  276.  
  277. 2. Data buffering control.  A separate control module exists for each
  278.    inter-processing-step data buffer.  This module is responsible for
  279.    invoking the processing steps that write or read that data buffer.
  280.  
  281. Each buffer controller sees the world as follows:
  282.  
  283. input data => processing step A => buffer => processing step B => output data
  284.                       |              |               |
  285.               ------------------ controller ------------------
  286.  
  287. The controller knows the dataflow requirements of steps A and B: how much data
  288. they want to accept in one chunk and how much they output in one chunk.  Its
  289. function is to manage its buffer and call A and B at the proper times.
  290.  
  291. A data buffer control module may itself be viewed as a processing step by a
  292. higher-level control module; thus the control modules form a binary tree with
  293. elementary processing steps at the leaves of the tree.
  294.  
  295. The control modules are objects.  A considerable amount of flexibility can
  296. be had by replacing implementations of a control module.  For example:
  297. * Merging of adjacent steps in the pipeline is done by replacing a control
  298.   module and its pair of processing-step modules with a single processing-
  299.   step module.  (Hence the possible merges are determined by the tree of
  300.   control modules.)
  301. * In some processing modes, a given interstep buffer need only be a "strip"
  302.   buffer large enough to accommodate the desired data chunk sizes.  In other
  303.   modes, a full-image buffer is needed and several passes are required.
  304.   The control module determines which kind of buffer is used and manipulates
  305.   virtual array buffers as needed.  One or both processing steps may be
  306.   unaware of the multi-pass behavior.
  307.  
  308. In theory, we might be able to make all of the data buffer controllers
  309. interchangeable and provide just one set of implementations for all.  In
  310. practice, each one contains considerable special-case processing for its
  311. particular job.  The buffer controller concept should be regarded as an
  312. overall system structuring principle, not as a complete description of the
  313. task performed by any one controller.
  314.  
  315.  
  316. *** Compression object structure ***
  317.  
  318. Here is a sketch of the logical structure of the JPEG compression library:
  319.  
  320.                                                  |-- Colorspace conversion
  321.                   |-- Preprocessing controller --|
  322.                   |                              |-- Downsampling
  323. Main controller --|
  324.                   |                            |-- Forward DCT, quantize
  325.                   |-- Coefficient controller --|
  326.                                                |-- Entropy encoding
  327.  
  328. This sketch also describes the flow of control (subroutine calls) during
  329. typical image data processing.  Each of the components shown in the diagram is
  330. an "object" which may have several different implementations available.  One
  331. or more source code files contain the actual implementation(s) of each object.
  332.  
  333. The objects shown above are:
  334.  
  335. * Main controller: buffer controller for the subsampled-data buffer, which
  336.   holds the preprocessed input data.  This controller invokes preprocessing to
  337.   fill the subsampled-data buffer, and JPEG compression to empty it.  There is
  338.   usually no need for a full-image buffer here; a strip buffer is adequate.
  339.  
  340. * Preprocessing controller: buffer controller for the downsampling input data
  341.   buffer, which lies between colorspace conversion and downsampling.  Note
  342.   that a unified conversion/downsampling module would probably replace this
  343.   controller entirely.
  344.  
  345. * Colorspace conversion: converts application image data into the desired
  346.   JPEG color space; also changes the data from pixel-interleaved layout to
  347.   separate component planes.  Processes one pixel row at a time.
  348.  
  349. * Downsampling: performs reduction of chroma components as required.
  350.   Optionally may perform pixel-level smoothing as well.  Processes a "row
  351.   group" at a time, where a row group is defined as Vmax pixel rows of each
  352.   component before downsampling, and Vk sample rows afterwards (remember Vk
  353.   differs across components).  Some downsampling or smoothing algorithms may
  354.   require context rows above and below the current row group; the
  355.   preprocessing controller is responsible for supplying these rows via proper
  356.   buffering.  The downsampler is responsible for edge expansion at the right
  357.   edge (i.e., extending each sample row to a multiple of 8 samples); but the
  358.   preprocessing controller is responsible for vertical edge expansion (i.e.,
  359.   duplicating the bottom sample row as needed to make a multiple of 8 rows).
  360.  
  361. * Coefficient controller: buffer controller for the DCT-coefficient data.
  362.   This controller handles MCU assembly, including insertion of dummy DCT
  363.   blocks when needed at the right or bottom edge.  When performing
  364.   Huffman-code optimization or emitting a multiscan JPEG file, this
  365.   controller is responsible for buffering the full image.  The equivalent of
  366.   one fully interleaved MCU row of subsampled data is processed per call,
  367.   even when the JPEG file is noninterleaved.
  368.  
  369. * Forward DCT and quantization: Perform DCT, quantize, and emit coefficients
  370.   in zigzag block order.  Works on one or more DCT blocks at a time.
  371.  
  372. * Entropy encoding: Perform Huffman or arithmetic entropy coding and emit the
  373.   coded data to the data destination module.  Works on one MCU per call.
  374.  
  375. In addition to the above objects, the compression library includes these
  376. objects:
  377.  
  378. * Master control: determines the number of passes required, controls overall
  379.   and per-pass initialization of the other modules.
  380.  
  381. * Marker writing: generates JPEG markers (except for RSTn, which is emitted
  382.   by the entropy encoder when needed).
  383.  
  384. * Data destination manager: writes the output JPEG datastream to its final
  385.   destination (e.g., a file).  The destination manager supplied with the
  386.   library knows how to write to a stdio stream; for other behaviors, the
  387.   surrounding application may provide its own destination manager.
  388.  
  389. * Memory manager: allocates and releases memory, controls virtual arrays
  390.   (with backing store management, where required).
  391.  
  392. * Error handler: performs formatting and output of error and trace messages;
  393.   determines handling of nonfatal errors.  The surrounding application may
  394.   override some or all of this object's methods to change error handling.
  395.  
  396. * Progress monitor: supports output of "percent-done" progress reports.
  397.   This object represents an optional callback to the surrounding application:
  398.   if wanted, it must be supplied by the application.
  399.  
  400. The error handler, destination manager, and progress monitor objects are
  401. defined as separate objects in order to simplify application-specific
  402. customization of the JPEG library.  A surrounding application may override
  403. individual methods or supply its own all-new implementation of one of these
  404. objects.  The object interfaces for these objects are therefore treated as
  405. part of the application interface of the library, whereas the other objects
  406. are internal to the library.
  407.  
  408. The error handler and memory manager are shared by JPEG compression and
  409. decompression; the progress monitor, if used, may be shared as well.
  410.  
  411.  
  412. *** Decompression object structure ***
  413.  
  414. Here is a sketch of the logical structure of the JPEG decompression library:
  415.  
  416.                                                |-- Entropy decoding
  417.                   |-- Coefficient controller --|
  418.                   |                            |-- Dequantize, Inverse DCT
  419. Main controller --|
  420.                   |                               |-- Upsampling
  421.                   |-- Postprocessing controller --|   |-- Colorspace conversion
  422.                                                   |-- Color quantization
  423.                                                   |-- Color precision reduction
  424.  
  425. As before, this diagram also represents typical control flow.  The objects
  426. shown are:
  427.  
  428. * Main controller: buffer controller for the subsampled-data buffer, which
  429.   holds the output of JPEG decompression proper.  This controller's primary
  430.   task is to feed the postprocessing procedure.  Some upsampling algorithms
  431.   may require context rows above and below the current row group; when this
  432.   is true, the main controller is responsible for managing its buffer so as
  433.   to make context rows available.  In the current design, the main buffer is
  434.   always a strip buffer; a full-image buffer is never required.
  435.  
  436. * Coefficient controller: buffer controller for the DCT-coefficient data.
  437.   This controller handles MCU disassembly, including deletion of any dummy
  438.   DCT blocks at the right or bottom edge.  When reading a multiscan JPEG
  439.   file, this controller is responsible for buffering the full image.
  440.   (Buffering DCT coefficients, rather than samples, is necessary to support
  441.   progressive JPEG.)  The equivalent of one fully interleaved MCU row of
  442.   subsampled data is processed per call, even when the source JPEG file is
  443.   noninterleaved.
  444.  
  445. * Entropy decoding: Read coded data from the data source module and perform
  446.   Huffman or arithmetic entropy decoding.  Works on one MCU per call.
  447.  
  448. * Dequantization and inverse DCT: like it says.  Note that the coefficients
  449.   buffered by the coefficient controller have NOT been dequantized; we
  450.   merge dequantization and inverse DCT into a single step for speed reasons.
  451.   When scaled-down output is asked for, simplified DCT algorithms may be used
  452.   that emit only 1x1, 2x2, or 4x4 samples per DCT block, not the full 8x8.
  453.   Works on one DCT block at a time.
  454.  
  455. * Postprocessing controller: buffer controller for the color quantization
  456.   input buffer, when quantization is in use.  (Without quantization, this
  457.   controller just calls the upsampler.)  For two-pass quantization, this
  458.   controller is responsible for buffering the full-image data.
  459.  
  460. * Upsampling: restores chroma components to full size.  (May support more
  461.   general output rescaling, too.  Note that if undersized DCT outputs have
  462.   been emitted by the DCT module, this module must adjust so that properly
  463.   sized outputs are created.)  Works on one row group at a time.  This module
  464.   also calls the color conversion module, so its top level is effectively a
  465.   buffer controller for the upsampling->color conversion buffer.  However, in
  466.   all but the highest-quality operating modes, upsampling and color
  467.   conversion are likely to be merged into a single step.
  468.  
  469. * Colorspace conversion: convert from JPEG color space to output color space,
  470.   and change data layout from separate component planes to pixel-interleaved.
  471.   Works on one pixel row at a time.
  472.  
  473. * Color quantization: reduce the data to colormapped form, using either an
  474.   externally specified colormap or an internally generated one.  This module
  475.   is not used for full-color output.  Works on one pixel row at a time; may
  476.   require two passes to generate a color map.  Note that the output will
  477.   always be a single component representing colormap indexes.  In the current
  478.   design, the output values are JSAMPLEs, so an 8-bit compilation cannot
  479.   quantize to more than 256 colors.  This is unlikely to be a problem in
  480.   practice.
  481.  
  482. * Color reduction: this module handles color precision reduction, e.g.,
  483.   generating 15-bit color (5 bits/primary) from JPEG's 24-bit output.
  484.   Not quite clear yet how this should be handled... should we merge it with
  485.   colorspace conversion???
  486.  
  487. Note that some high-speed operating modes might condense the entire
  488. postprocessing sequence to a single module (upsample, color convert, and
  489. quantize in one step).
  490.  
  491. In addition to the above objects, the decompression library includes these
  492. objects:
  493.  
  494. * Master control: determines the number of passes required, controls overall
  495.   and per-pass initialization of the other modules.
  496.  
  497. * Marker reading: decodes JPEG markers (except for RSTn).
  498.  
  499. * Data source manager: supplies the input JPEG datastream.  The source
  500.   manager supplied with the library knows how to read from a stdio stream;
  501.   for other behaviors, the surrounding application may provide its own source
  502.   manager.
  503.  
  504. * Memory manager: same as for compression library.
  505.  
  506. * Error handler: same as for compression library.
  507.  
  508. * Progress monitor: same as for compression library.
  509.  
  510. As with compression, the data source manager, error handler, and progress
  511. monitor are candidates for replacement by a surrounding application.
  512.  
  513.  
  514. *** Data formats ***
  515.  
  516. Arrays of pixel sample values use the following data structure:
  517.  
  518.     typedef something JSAMPLE;        a pixel component value, 0..MAXJSAMPLE
  519.     typedef JSAMPLE *JSAMPROW;        ptr to a row of samples
  520.     typedef JSAMPROW *JSAMPARRAY;    ptr to a list of rows
  521.     typedef JSAMPARRAY *JSAMPIMAGE;    ptr to a list of color-component arrays
  522.  
  523. The basic element type JSAMPLE will typically be one of unsigned char,
  524. (signed) char, or short.  Short will be used if samples wider than 8 bits are
  525. to be supported (this is a compile-time option).  Otherwise, unsigned char is
  526. used if possible.  If the compiler only supports signed chars, then it is
  527. necessary to mask off the value when reading.  Thus, all reads of JSAMPLE
  528. values must be coded as "GETJSAMPLE(value)", where the macro will be defined
  529. as "((value) & 0xFF)" on signed-char machines and "((int) (value))" elsewhere.
  530.  
  531. With these conventions, JSAMPLE values can be assumed to be >= 0.  This helps
  532. simplify correct rounding during downsampling, etc.  The JPEG standard's
  533. specification that sample values run from -128..127 is accommodated by
  534. subtracting 128 just as the sample value is copied into the source array for
  535. the DCT step (this will be an array of signed ints).  Similarly, during
  536. decompression the output of the IDCT step will be immediately shifted back to
  537. 0..255.  (NB: different values are required when 12-bit samples are in use.
  538. The code is written in terms of MAXJSAMPLE and CENTERJSAMPLE, which will be
  539. defined as 255 and 128 respectively in an 8-bit implementation, and as 4095
  540. and 2048 in a 12-bit implementation.)
  541.  
  542. We use a pointer per row, rather than a two-dimensional JSAMPLE array.  This
  543. choice costs only a small amount of memory and has several benefits:
  544. * Code using the data structure doesn't need to know the allocated width of
  545.   the rows.  This simplifies edge expansion/compression, since we can work
  546.   in an array that's wider than the logical picture width.
  547. * Indexing doesn't require multiplication; this is a performance win on many
  548.   machines.
  549. * Arrays with more than 64K total elements can be supported even on machines
  550.   where malloc() cannot allocate chunks larger than 64K.
  551. * The rows forming a component array may be allocated at different times
  552.   without extra copying.  This trick allows some speedups in smoothing steps
  553.   that need access to the previous and next rows.
  554.  
  555. Note that each color component is stored in a separate array; we don't use the
  556. traditional layout in which the components of a pixel are stored together.
  557. This simplifies coding of modules that work on each component independently,
  558. because they don't need to know how many components there are.  Furthermore,
  559. we can read or write each component to a temporary file independently, which
  560. is helpful when dealing with noninterleaved JPEG files.
  561.  
  562. In general, a specific sample value is accessed by code such as
  563.     GETJSAMPLE(image[colorcomponent][row][col])
  564. where col is measured from the image left edge, but row is measured from the
  565. first sample row currently in memory.  Either of the first two indexings can
  566. be precomputed by copying the relevant pointer.
  567.  
  568.  
  569. Since most image-processing applications prefer to work on images in which
  570. the components of a pixel are stored together, the data passed to or from the
  571. surrounding application uses the traditional convention: a single pixel is
  572. represented by N consecutive JSAMPLE values, and an image row is an array of
  573. (# of color components)*(image width) JSAMPLEs.  One or more rows of data can
  574. be represented by a pointer of type JSAMPARRAY in this scheme.  This scheme is
  575. converted to component-wise storage inside the JPEG library.  (Applications
  576. that want to skip JPEG preprocessing or postprocessing will have to contend
  577. with component-wise storage.)
  578.  
  579.  
  580. Arrays of DCT-coefficient values use the following data structure:
  581.  
  582.     typedef short JCOEF;        a 16-bit signed integer
  583.     typedef JCOEF JBLOCK[DCTSIZE2];    an 8x8 block of coefficients
  584.     typedef JBLOCK *JBLOCKROW;        ptr to one horizontal row of 8x8 blocks
  585.     typedef JBLOCKROW *JBLOCKARRAY;    ptr to a list of such rows
  586.     typedef JBLOCKARRAY *JBLOCKIMAGE;    ptr to a list of color component arrays
  587.  
  588. The underlying type is at least a 16-bit signed integer; while "short" is big
  589. enough on all machines of interest, on some machines it is preferable to use
  590. "int" for speed reasons, despite the storage cost.  Coefficients are grouped
  591. into 8x8 blocks (but we always use #defines DCTSIZE and DCTSIZE2 rather than
  592. "8" and "64").  The contents of a block may be either in "natural" or
  593. zigzagged order, and may be true values or divided by the quantization
  594. coefficients, depending on where the block is in the processing pipeline.
  595.  
  596. Notice that the allocation unit is now a row of 8x8 blocks, corresponding to
  597. eight rows of samples.  Otherwise the structure is much the same as for
  598. samples, and for the same reasons.
  599.  
  600. On machines where malloc() can't handle a request bigger than 64Kb, this data
  601. structure limits us to rows of less than 512 JBLOCKs, or a picture width of
  602. 4000+ pixels.  This seems an acceptable restriction.
  603.  
  604.  
  605. On 80x86 machines, the bottom-level pointer types (JSAMPROW and JBLOCKROW)
  606. must be declared as "far" pointers, but the upper levels can be "near"
  607. (implying that the pointer lists are allocated in the DS segment).
  608. We use a #define symbol FAR, which expands to the "far" keyword when
  609. compiling on 80x86 machines and to nothing elsewhere.
  610.  
  611.  
  612. *** Suspendable processing ***
  613.  
  614. In some applications it is desirable to use the JPEG library as an
  615. incremental, memory-to-memory filter.  In this situation the data source or
  616. destination may be a limited-size buffer, and we can't rely on being able to
  617. empty or refill the buffer at arbitrary times.  Instead the application would
  618. like to have control return from the library at buffer overflow/underrun, and
  619. then resume compression or decompression at a later time.
  620.  
  621. This scenario is supported for simple cases, namely, single-pass processing
  622. of single-scan JPEG files.  (For anything more complex, we recommend that the
  623. application "bite the bullet" and develop real multitasking capability.)  The
  624. libjpeg.doc file goes into more detail about the usage and limitations of
  625. this capability; here we address the implications for library structure.
  626.  
  627. The essence of the problem is that the entropy codec (coder or decoder) must
  628. be prepared to stop at arbitrary times.  In turn, the controllers that call
  629. the entropy codec must be able to stop before having produced or consumed all
  630. the data that they normally would handle in one call.  That part is reasonably
  631. straightforward: we make the controller call interfaces include "progress
  632. counters" which indicate the number of data chunks successfully processed, and
  633. we require callers to test the counter rather than just assume all of the data
  634. was processed.
  635.  
  636. Rather than trying to restart at an arbitrary point, the current Huffman
  637. codecs are designed to restart at the beginning of the current MCU after a
  638. suspension due to buffer overflow/underrun.  At the start of each call, the
  639. codec's internal state is loaded from permanent storage (in the JPEG object
  640. structures) into local variables.  On successful completion of the MCU, the
  641. permanent state is updated.  (This copying is not very expensive, and may even
  642. lead to *improved* performance if the local variables can be registerized.)
  643. If a suspension occurs, the codec simply returns without updating the state,
  644. thus effectively reverting to the start of the MCU.  Note that this implies
  645. leaving some data unprocessed in the source/destination buffer (ie, the
  646. compressed partial MCU).  The data source/destination module interfaces are
  647. specified so as to make this possible.  This also implies that the data buffer
  648. must be large enough to hold a worst-case compressed MCU; a couple thousand
  649. bytes should be enough.
  650.  
  651. This design would probably not work for an arithmetic codec, since its
  652. modifiable state is quite large and couldn't be copied cheaply.  Instead it
  653. would have to suspend and resume exactly at the point of the buffer end.
  654. Also, a progressive JPEG decoder would have some problems with having already
  655. updated the output DCT coefficient buffer, since progressive decoding depends
  656. on the prior state of the coefficient buffer.  This case might also have to be
  657. handled by exact restart.  Currently I expect that IJG will just not support
  658. suspendable operation in these cases (when and if we implement them at all).
  659.  
  660. The JPEG marker reader is designed to cope with suspension at an arbitrary
  661. point.  It does so by backing up to the start of the marker parameter segment,
  662. so the data buffer must be big enough to hold the largest marker of interest.
  663. Again, a couple KB should be adequate.  (A special "skip" convention is used
  664. to bypass COM and APPn markers, so these can be larger than the buffer size
  665. without causing problems; otherwise a 64K buffer would be needed in the worst
  666. case.)
  667.  
  668. The JPEG marker writer currently does *not* cope with suspension.  I feel that
  669. this is not necessary; it is much easier simply to require the application to
  670. ensure there is enough buffer space before starting.  (An empty 2K buffer is
  671. more than sufficient for the header markers; and ensuring there are a dozen or
  672. two bytes available before calling jpeg_finish_compress() will suffice for the
  673. trailer.)  Again, this would not work for writing multi-scan JPEG files, but
  674. we simply do not intend to support that capability with suspension.
  675.  
  676.  
  677. *** Memory manager services ***
  678.  
  679. The JPEG library's memory manager controls allocation and deallocation of
  680. memory, and it manages large "virtual" data arrays on machines where the
  681. operating system does not provide virtual memory.  Note that the same
  682. memory manager serves both compression and decompression operations.
  683.  
  684. In all cases, allocated objects are tied to a particular compression or
  685. decompression master record, and they will be released when that master
  686. record is destroyed.
  687.  
  688. The memory manager does not provide explicit deallocation of objects.
  689. Instead, objects are created in "pools" of free storage, and a whole pool
  690. can be freed at once.  This approach helps prevent storage-leak bugs, and
  691. it speeds up operations whenever malloc/free are slow (as they often are).
  692. The pools can be regarded as lifetime identifiers for objects.  Two
  693. pools/lifetimes are defined:
  694.   * JPOOL_PERMANENT    lasts until master record is destroyed
  695.   * JPOOL_IMAGE        lasts until done with image (JPEG datastream)
  696. Permanent lifetime is used for parameters and tables that should be carried
  697. across from one datastream to another; this includes all application-visible
  698. parameters.  Image lifetime is used for everything else.  (A third lifetime,
  699. JPOOL_PASS = one processing pass, was originally planned.  However it was
  700. dropped as not being worthwhile.  The actual usage patterns are such that the
  701. peak memory usage would be about the same anyway; and having per-pass storage
  702. substantially complicates the virtual memory allocation rules --- see below.)
  703.  
  704. The memory manager deals with three kinds of object:
  705. 1. "Small" objects.  Typically these require no more than 10K-20K total.
  706. 2. "Large" objects.  These may require tens to hundreds of K depending on
  707.    image size.  Semantically they behave the same as small objects, but we
  708.    distinguish them for two reasons:
  709.      * On MS-DOS machines, large objects are referenced by FAR pointers,
  710.        small objects by NEAR pointers.
  711.      * Pool allocation heuristics may differ for large and small objects.
  712.    Note that individual "large" objects cannot exceed the size allowed by
  713.    type size_t, which may be 64K or less on some machines.
  714. 3. "Virtual" objects.  These are large 2-D arrays of JSAMPLEs or JBLOCKs
  715.    (typically large enough for the entire image being processed).  The
  716.    memory manager provides stripwise access to these arrays.  On machines
  717.    without virtual memory, the rest of the array may be swapped out to a
  718.    temporary file.
  719.  
  720. (Note: JSAMPARRAY and JBLOCKARRAY data structures are a combination of large
  721. objects for the data proper and small objects for the row pointers.  For
  722. convenience and speed, the memory manager provides single routines to create
  723. these structures.  Similarly, virtual arrays include a small control block
  724. and a JSAMPARRAY or JBLOCKARRAY working buffer, all created with one call.)
  725.  
  726. In the present implementation, virtual arrays are only permitted to have image
  727. lifespan.  (Permanent lifespan would not be reasonable, and pass lifespan is
  728. not very useful since a virtual array's raison d'etre is to store data for
  729. multiple passes through the image.)  We also expect that only "small" objects
  730. will be given permanent lifespan, though this restriction is not required by
  731. the memory manager.
  732.  
  733. In a non-virtual-memory machine, some performance benefit can be gained by
  734. making the in-memory buffers for virtual arrays be as large as possible.
  735. (For small images, the buffers might fit entirely in memory, so blind
  736. swapping would be very wasteful.)  The memory manager will adjust the height
  737. of the buffers to fit within a prespecified maximum memory usage.  In order
  738. to do this in a reasonably optimal fashion, the manager needs to allocate all
  739. of the virtual arrays at once.  Therefore, there isn't a one-step allocation
  740. routine for virtual arrays; instead, there is a "request" routine that simply
  741. allocates the control block, and a "realize" routine (called just once) that
  742. determines space allocation and creates all of the actual buffers.  The
  743. realize routine must allow for space occupied by non-virtual large objects.
  744. (We don't bother to factor in the space needed for small objects, on the
  745. grounds that it isn't worth the trouble.)
  746.  
  747. To support all this, we establish the following protocol for doing business
  748. with the memory manager:
  749.   1. Modules must request virtual arrays (which may have only image lifespan)
  750.      during the global selection phase, i.e., in their jinit_xxx routines.
  751.   2. All "large" objects (including JSAMPARRAYs and JBLOCKARRAYs) must also be
  752.      allocated at global selection time.
  753.   3. realize_virt_arrays will be called at the completion of global selection.
  754.      The above conventions ensure that sufficient information is available
  755.      for it to choose a good size for virtual array buffers.
  756. Small objects of any lifespan may be allocated at any time.  We expect that
  757. the total space used for small objects will be small enough to be negligible
  758. in the realize_virt_arrays computation.
  759.  
  760. In a virtual-memory machine, we simply pretend that the available space is
  761. infinite, thus causing realize_virt_arrays to decide that it can allocate all
  762. the virtual arrays as full-size in-memory buffers.  The overhead of the
  763. virtual-array access protocol is very small when no swapping occurs.
  764.  
  765.  
  766. *** Memory manager internal structure ***
  767.  
  768. To isolate system dependencies as much as possible, we have broken the
  769. memory manager into two parts.  There is a reasonably system-independent
  770. "front end" (jmemmgr.c) and a "back end" that contains only the code
  771. likely to change across systems.  All of the memory management methods
  772. outlined above are implemented by the front end.  The back end provides
  773. the following routines for use by the front end (none of these routines
  774. are known to the rest of the JPEG code):
  775.  
  776. jpeg_mem_init, jpeg_mem_term    system-dependent initialization/shutdown
  777.  
  778. jpeg_get_small, jpeg_free_small    interface to malloc and free library routines
  779.                 (or their equivalents)
  780.  
  781. jpeg_get_large, jpeg_free_large    interface to FAR malloc/free in MSDOS machines;
  782.                 else usually the same as
  783.                 jpeg_get_small/jpeg_free_small
  784.  
  785. jpeg_mem_available        estimate available memory
  786.  
  787. jpeg_open_backing_store        create a backing-store object
  788.  
  789. read_backing_store,        manipulate a backing-store object
  790. write_backing_store,
  791. close_backing_store
  792.  
  793. On some systems there will be more than one type of backing-store object
  794. (specifically, in MS-DOS a backing store file might be an area of extended
  795. memory as well as a disk file).  jpeg_open_backing_store is responsible for
  796. choosing how to implement a given object.  The read/write/close routines
  797. are method pointers in the structure that describes a given object; this
  798. lets them be different for different object types.
  799.  
  800. It may be necessary to ensure that backing store objects are explicitly
  801. released upon abnormal program termination.  For example, MS-DOS won't free
  802. extended memory by itself.  To support this, we will expect the main program
  803. or surrounding application to arrange to call self_destruct (typically via
  804. jpeg_destroy) upon abnormal termination.  This may require a SIGINT signal
  805. handler or equivalent.  We don't want to have the back end module install its
  806. own signal handler, because that would pre-empt the surrounding application's
  807. ability to control signal handling.
  808.  
  809. The IJG distribution includes several memory manager back end implementations.
  810. Usually the same back end should be suitable for all applications on a given
  811. system, but it is possible for an application to supply its own back end at
  812. need.
  813.  
  814.  
  815. *** Implications of DNL marker ***
  816.  
  817. Some JPEG files may use a DNL marker to postpone definition of the image
  818. height (this would be useful for a fax-like scanner's output, for instance).
  819. In these files the SOF marker claims the image height is 0, and you only
  820. find out the true image height at the end of the first scan.
  821.  
  822. We could read these files as follows:
  823. 1. Upon seeing zero image height, replace it by 65535 (the maximum allowed).
  824. 2. When the DNL is found, update the image height in the global image
  825.    descriptor.
  826. This implies that control modules must avoid making copies of the image
  827. height, and must re-test for termination after each MCU row.  This would
  828. be easy enough to do.
  829.  
  830. In cases where image-size data structures are allocated, this approach will
  831. result in very inefficient use of virtual memory or much-larger-than-necessary
  832. temporary files.  This seems acceptable for something that probably won't be a
  833. mainstream usage.  People might have to forgo use of memory-hogging options
  834. (such as two-pass color quantization or noninterleaved JPEG files) if they
  835. want efficient conversion of such files.  (One could improve efficiency by
  836. demanding a user-supplied upper bound for the height, less than 65536; in most
  837. cases it could be much less.)
  838.  
  839. The standard also permits the SOF marker to overestimate the image height,
  840. with a DNL to give the true, smaller height at the end of the first scan.
  841. This would solve the space problems if the overestimate wasn't too great.
  842. However, it implies that you don't even know whether DNL will be used.
  843.  
  844. This leads to a couple of very serious objections:
  845. 1. Testing for a DNL marker must occur in the inner loop of the decompressor's
  846.    Huffman decoder; this implies a speed penalty whether the feature is used
  847.    or not.
  848. 2. There is no way to hide the last-minute change in image height from an
  849.    application using the decoder.  Thus *every* application using the IJG
  850.    library would suffer a complexity penalty whether it cared about DNL or
  851.    not.
  852. We currently do not support DNL because of these problems.
  853.  
  854. A different approach is to insist that DNL-using files be preprocessed by a
  855. separate program that reads ahead to the DNL, then goes back and fixes the SOF
  856. marker.  This is a much simpler solution and is probably far more efficient.
  857. Even if one wants piped input, buffering the first scan of the JPEG file needs
  858. a lot smaller temp file than is implied by the maximum-height method.  For
  859. this approach we'd simply treat DNL as a no-op in the decompressor (at most,
  860. check that it matches the SOF image height).
  861.  
  862. We will not worry about making the compressor capable of outputting DNL.
  863. Something similar to the first scheme above could be applied if anyone ever
  864. wants to make that work.
  865.